The unique properties of PUFs provide several advantages to cryptographic constructions. In general, PUFs may provide some or all of three main advantages: (1) eliminating private key storage, (2) providing tamper detection, and (3) establishing a hardware root-of-trust. Private key storage can be eliminated by evaluating a PUF to dynamically regenerate a value unique to an identified piece of hardware having that PUF. As to tamper detection, a PUF's unclonable properties (e.g., wire delays, resistance) may be such that modification to the PUF irreversibly alters the PUF's mapping from challenges (inputs) to responses (outputs) after enrollment (however, not against malicious modifications before enrollment, e.g., Becker et al., “Stealthy Dopant-Level Hardware Trojans,” Cryptographic Hardware and Embedded Systems—CHES 2013, volume 8086 of Lecture Notes in Computer Science, pages 197-214, Springer, 2013). These PUF properties may be used to produce a hardware-unique, tamper-protected value from which a hardware root-of-trust can be established.
Rührmair et al. (“Modeling Attacks on Physical Unclonable Functions,” Proceedings of the 17th ACM conference on Computer and communications security, CCS '10, pages 237-249, ACM, 2010) define three distinct classes of PUF devices:                A Weak PUF is typically used only to derive a secret key. The challenge space may be limited, and the response space is assumed to never be revealed. Typical constructions include the SRAM (Holcomb et al., “Initial SRAM State as a Fingerprint and Source of True Random Numbers for RFID Tags,” In Proceedings of the Conference on RFID Security, 2007), Butterfly (Kumar et al., “Extended abstract: The Butterfly PUF Protecting IP on Every FPGA,” IEEE International Workshop on Hardware-Oriented Security and Trust, pages 67-70, 2008), Arbiter (Lee et al., “A technique to build a secret key in integrated circuits for identification and authentication applications,” IEEE Symposium on VLSI Circuits: Digest of Technical Papers, pages 176-179, 2004), Ring Oscillator (Suh et al., “Physical Unclonable Functions for Device Authentication and Secret Key Generation,” Proceedings of the 14th annual Design Automation Conference, DAC '07, pages 9-14, ACM, 2007), and Coating (Tuyls et al., “Read-Proof Hardware from Protective Coatings,” Proceedings of the 8th international conference on Cryptographic Hardware and Embedded Systems, CHES '06, pages 369-383, Springer, 2006) PUFs.        A Strong PUF is assumed to be (i) physically impossible to clone, (ii) impossible to collect a complete set of challenge response pairs in a reasonable time (typically taken to be on the order of weeks), and (iii) difficult to predict the response to a random challenge. For example, the super-high information content (SHIC) PUF described by Rührmair (“Applications of High-Capacity Crossbar Memories in Cryptography,” IEEE Trans. Nanotechnol., volume 10, no. 3:489-498, 2011) may be considered a Strong PUF.        A Controlled PUF satisfies all of the criteria for strong PUFs, and additionally implements an auxiliary control unit capable of computing more advanced functionalities to cryptographically augment protocols.        
PUF output is noisy in that it varies slightly despite evaluating the same input. This is generally addressed with fuzzy extraction, a method developed to eliminate noise in biometric measurements. (See Juels et al., “A Fuzzy Commitment Scheme,” Proceedings of the 6th ACM conference on Computer and Communications Security, CCS '99, pages 28-36, ACM, 1999). Fuzzy extraction may in part be employed within a device having a PUF such as within an auxiliary control unit, such that the output is constant for a fixed input. Fuzzy extraction (or reverse fuzzy extraction) may for example employ a “secure sketch,” as described by Juels et al. to store a sensitive value pipriv to be reconstructed and a helper string helperi for recovering pipriv. A secure sketch SS for input string O, where ECC is a binary (n, k, 2t+1) error correcting code of length n capable of correcting t errors and pipriv←{0, 1}k is a k-bit value, may for example be defined as SS(O; pipriv)=O⊕EECC(pipriv). The original value V then may be reproduced given the helper string helperi and an input O′ within a maximum Hamming distance t of O using a decoding scheme D for the error-correcting code ECC and O′, as D(helperi⊕O′)=D(O⊕ECC(pipriv)⊕O′)=pipriv.
A physical unclonable function Pd: {0, 1}K1→{0, 1}K2 bound to a device d preferably exhibits the following properties:                1. Unclonability: Pr[dist(y,x)≤t|x→UK1, y→P(x), z→P′]≤ϵ1, the probability of duplicating PUF P with a clone PUF P′ such that their output distributions are t-statistically close is less than some sufficiently small ϵ1.        2. Unpredictability: It is desirable that an adversary cannot predict a device's PUF response r for a challenge c with more than negligible probability (at least without physical access to the device), and that helper data does not reveal anything to an adversary about PUF responses. Assuming that all entities are bound to probabilistic polynomial-time (PPT), i.e., can only efficiently perform computation requiring polynomially many operations with respect to a global security parameter λ (which refers to the number of bits in the relevant parameter), Ad(κ2):=Pr[r=r′], denoting the probability of the adversary  guessing the correct response r of the PUF P to the challenge c, is preferably negligible in κ2. This can be assessed, for example, through a game between an adversary  and a PUF device P:{0, 1}κ1{0, 1}κ2 mapping input strings from the challenge space P of length κ1 to the response space P of length κ2 where λ is the security parameter for the protocol, given in unary as 1λ.        
PUF-PRED: PUF Prediction GameAdversary    PUF Device P(1)ci ∈    P ⊂    P,→0 ≤ i ≤ poly(λ)←ri = P(ci) ∈    P(2)   P ⊂    P,0 ≤ i ≤ poly(λ)(3)Challenge c ∉    P→(4)c′i ∈    ′P ⊂    P,→c ∉    ′P,0 ≤ i ≤ poly(λ)←r′i = P(c′i) ∈    ′P(5)   ′P ⊂    P,0 ≤ i ≤ poly(λ)(6)Guess r′     P(c)
The game proceeds as follows:                1. The adversary  issues polynomially many (w.r.t. the security parameter λ) challenges ciϵP to the PUF device P, where the challenge set P is a proper subset of the entire challenge space P.        2. The PUF device P returns the responses {ri|ri←P(ci)} to .        3. The adversary  eventually outputs a challenge c that was not in the original set of challenge queries P. The adversary is not allowed to query the PUF device P on the committed challenge c.        4. The adversary  may once again issue a new set of polynomially many challenges c′iϵP to the PUF device P. The adversary is not allowed to query the PUF device P on the committed challenge c.        5. The PUF device P returns the responses {r′i|r′i←P(c′i)} to .        6. The adversary  eventually outputs a guess r′ for P's response to the committed challenge c.        
The adversary only wins the game when guess r′ is equal to P's actual response r←P(c) to 's committed challenge c. (As noted, the PUF's output is noisy and will vary slightly on any fixed input, so the equality is typically taken with respect to the output of a fuzzy extractor (e.g., Dodis et al., “Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data,” SIAM J. Comput., volume 38, no. 1:97-139, 2008)).                3. Robustness: Pr[dist(y, z)>t|x←Uκ1, y←P(x), z←P(x)]≤ϵ2, i.e., the probability of a fixed PUF P yielding responses t-distant on the same input x is less than some sufficiently small ϵ2.        4. Indistinguishability: The output of the PUF device (typically fuzzy extractor output) preferably is computationally indistinguishable from a random string of the same length l, such that a PPT adversary 's advantage Ad(l) is at most negligibly more than ½. The indistinguishability of a PUF can be assessed, for example, through a game in which an adversary  is asked to differentiate between the output r of the fuzzy extractor for a PUF P and a randomly chosen string s ϵ{0, 1}l of the same length l.        
PUF-IND: PUF Indistinguishability GameAdversary    PUF Device P(1)ci ∈     ⊂    P,→Ri ← rand ∈ {0, 1}λ0 ≤ i ≤ poly(λ)Hi ← ECC(Ri) ⊕ P(c)←Hi ∈    P ⊂    P,(2)0 ≤ i ≤ poly(λ)(3)ci ∈     ⊂    P,→0 ≤ i ≤ poly(λ)←Ri ∈    P ⊂    P,(4)0 ≤ i ≤ poly(λ)(5)Challenge c ∉    →b ∈ {0, 1}←b(s ∈ {0, 1}l) +(6)(1 − b)(Ri),Ri = D(Hi ⊕ P(c))(7)c′i ∈     ⊂    P,→c ≠ c′i,0 ≤ i ≤ poly(λ)←R′i ∈    P ⊂    P(8)0 ≤ i ≤ poly(λ)(9)Guess b′     b→
This game proceeds as follows:                1. Adversary  executes the enrollment phase on any challenge ciϵP.        2. The PUF device returns the corresponding helper string Hi, which blinds the error corrected sensitive value ECC(Ri) with the output of the PUF P(c). Denote this set of challenge-helper pairs (ci, Hi) as .        3. Adversary  now requests the PUF response ri=P(ci) for any ciϵ. Denote the set of requested challenges in this step .        4. For all requests ciϵ, the PUF device returns the set {ri|ri←P(ci)}.        5. Adversary  selects a challenge cϵ, such that  has Hi but not Ri for c. The PUF device chooses a bit bϵ{0, 1} uniformly at random.        6. If b=0,  is given Ri=D(Hi⊕P(c)). Otherwise, if b=1 then  is given a random string sϵ{0, 1}l.        7. Adversary  is allowed to query the PUF device for c′iϵ so long as no c′i=c.        8. For all requests c′i≠c, the PUF device returns the set {r′i|r′i→P(c′i)}.        9. The adversary outputs a guess bit b′, and succeeds when b′=b.Related assessments of PUFs are provided by Hori et al., “Quantitative and Statistical Performance Evaluation of Arbiter Physical Unclonable Functions on FPGAs,” 2010 International Conference on Reconfigurable Computing and FPGAs (ReConFig), pages 298-303, 2010; Maiti, A Systematic Approach to Design an Efficient Physical Unclonable Function, dissertation, Virginia Tech, 2012, and others.        
Literature on physical unclonable functions evaluates the properties of PUF hardware design (e.g., Gassend et al., “Silicon Physical Random Functions,” Proceedings of the 9th ACM conference on Computer and communications security, CCS '02, pages 148-160, ACM, 2002; Katzenbeisser et al., “PUFs: Myth, Fact or Busted? A Security Evaluation of Physically Unclonable Functions (PUFs) Cast in Silicon,” Cryptographic Hardware and Embedded Systems—CHES '12, pages 283-301, Springer, 2012; Ravikanth, Physical one-way functions, Ph.D. thesis, 2001; Rührmair et al., “Applications of High-Capacity Crossbar Memories in Cryptography,” IEEE Trans. Nanotechnol., volume 10, no. 3:489-498, 2011; Suh et al., “Physical Unclonable Functions for Device Authentication and Secret Key Generation,” Proceedings of the 4th annual Design Automation Conference, DAC '07, pages 9-14, ACM, 2007; Yu et al., “Recombination of Physical Unclonable Functions,” GOMACTech, 2010), provides formal theoretical models of PUF properties, and designs protocols around those definitions (cf. Armknecht et al., “A Formalization of the Security Features of Physical Functions,” Proceedings of the 2011 IEEE Symposium on Security and Privacy, SP '11, pages 397-412, IEEE Computer Society, 2011; Brzuska et al., “Physically Uncloneable Functions in the Universal Composition Framework,” Advances in Cryptology—CRYPTO 2011—31st Annual Cryptology Conference, volume 6841 of Lecture Notes in Computer Science, page 51, Springer, 2011; Frikken et al., “Robust Authentication using Physically Unclonable Functions,” Information Security, volume 5735 of Lecture Notes in Computer Science, pages 262-277, Springer, 2009; Handschuh et al., “Hardware Intrinsic Security from Physically Unclonable Functions,” Towards Hardware-Intrinsic Security, Information Security and Cryptography, pages 39-53, Springer, 2010; Kirkpatrick et al., “PUF ROKs: A Hardware Approach to Read-Once Keys,” Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, ASIACCS '11, pages 155-164, ACM, 2011; Paral et al., “Reliable and Efficient PUF-based Key Generation using Pattern Matching,” IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), pages 128-133, 2011; Rührmair et al., “PUFs in Security Protocols: Attack Models and Security Evaluations,” 2013 IEEE Symposium on Security and Privacy, volume 0:286-300, 2013; van Dijk et al., “Physical Unclonable Functions in Cryptographic Protocols: Security Proofs and Impossibility Results,” Cryptology ePrint Archive, Report 2012/228, 2012; Wu et al., “On Foundation and Construction of Physical Unclonable Functions,” 2010; Yu et al., “Lightweight and Secure PUF Key Storage using Limits of Machine Learning,” Proceedings of the 13th international conference on Cryptographic Hardware and Embedded Systems, CHES'11, pages 358-373, Springer, 2011).
Prior art PUF-based protocols fall into two broad categories: (1) a simple challenge-response provisioning process like the one described below in Protocol 1, or (2) cryptographic augmentation of a device's PUF response such that the raw PUF output never leaves the device. These approaches may require external entities to handle auxiliary information (e.g., challenges and their associated helper data) that is unsupported or superfluous in existing public key cryptography standards, and/or involve a hardware device authenticating to a challenge applied during an initial enrollment process, and/or are premised on the hardware device always recovering essentially the same response to a given challenge.
While a given challenge-response pair reflects the hardware state of a device when the pair was collected, the device will age and its hardware state drift over time. As the PUF hardware ages, the number of errors present in the responses may increase. Maiti et al. (“The Impact of Aging on an FPGA-Based Physical Unclonable Function,” International Conference on Field Programmable Logic and Applications (FPL), pages 151-156, 2011) study the effects of simulated aging on PUF hardware by purposefully stressing the devices beyond normal operating conditions. By varying both temperature and voltage, the authors were able to show a drift in the intra-PUF variation that, over time, will lead to false negatives. Maiti et al. note that the error drift strictly affected the intra-PUF error rate distribution tending towards the maximum entropy rate of 50%. After enough time elapses, the hardware device may no longer be able to recover the proper response for the enrolled challenge.
For example, assume that a specific challenge ci is issued to a device during enrollment, with the device returning a public token {commitmenti, helperi} that links the device's hardware identity with the challenge c. To be authenticated, the device uses the pair {ci,helperi} to recover its private identity pipriv. As shown in FIG. 10, over time the PUF hardware may reach a time (e.g., at time τ=5 in the example of FIG. 10, which for simplicity assumes a drift that occurs linearly over time) at which hardware aging has increased the errors beyond the device's error correction limit, and the device is no longer able to reliably regenerate its private key.
Kirkpatrick et al. (“Software Techniques to Combat Drift in PUF-based Authentication Systems,” Workshop on Secure Component and System Identification, 2010) describe a method for detecting hardware aging drift, and responding by updating the device's challenge-commitment pair stored on an external server. This approach requires that the server maintain auxiliary information in the form of challenge-commitment pairs, however, and that a periodic protocol be executed between the server and the device.
Another challenge facing PUF-based systems is side channel attacks, which seek to observe and analyze auxiliary environmental variables to deduce information about the sensitive PUF output. For example, electromagnetic (EM) analysis (e.g., Merli et al., “Semi-invasive EM Attack on FPGA RO PUFs and Countermeasures,” Proceedings of the Workshop on Embedded Systems Security, WESS '11, pages 2:1-2:9, ACM, 2011; Merli et al., “Side-Channel Analysis of PUFs and Fuzzy Extractors,” Trust and Trustworthy Computing, volume 6740 of Lecture Notes in Computer Science, pages 33-47, Springer, 2011; Schuster, Side-Channel Analysis of Physical Unclonable Functions (PUFs), Master's thesis, Technische Universitat Munchen, 2010) extracts PUF output bits by observing changing EM fields during device operation. Another side channel attack methodology is (simple or differential) power analysis (e.g., Karakoyunlu et al., “Differential template attacks on PUF enabled cryptographic devices,” IEEE International Workshop on Information Forensics and Security (WIFS), pages 1-6, 2010; Kocher et al., “Introduction to Differential Power Analysis,” Cryptography Research, Inc., 2011; Kocher et al., “Differential Power Analysis,” Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '99, pages 388-397, Springer, 1999; Rührmair et al., “Power and Timing Side Channels for PUFs and their Efficient Exploitation,” 2013), where power traces are collected from a device and analyzed to extract sensitive information (e.g., PUF output bits). Over many observations of a device recovering essentially the same response to a fixed challenge, an adversary can discover the sensitive PUF output.
While it is known that the effectiveness of side channel attacks may in some systems be reduced by introducing randomness (Coron, “Resistance Against Differential Power Analysis For Elliptic Curve Cryptosystems,” Cryptographic Hardware and Embedded Systems, volume 1717 of Lecture Notes in Computer Science, pages 292-302, Springer, 1999), disguising sensitive values in this way may leave some vulnerability since the underlying values remain static and/or introduce additional complexity and/or processing overhead.